package lib

import "sort"

//link to 77 78
func init() {
	Probs = append(Probs, Problem{
		Num:         90,
		Discription: "求存在重复元素的集合的所有子集",
		Level:       1,
		Labels: map[string]int{
			"排序": 1,
			"递归": 1,
			"去重": 1,
		},
	})
}

func SubsetsWithDup(nums []int) [][]int {
	//先排序，把所有相同的元素放到连续的位置
	sort.Ints(nums)
	res := [][]int{{}}
	comb := make([]int, 0)
	var dfs func(int)
	dfs = func(start int) {
		if start >= len(nums) {
			return
		}

		for i := start; i < len(nums); i++ {
			//保证同一个位置不会选到相同的元素
			if i > start && nums[i] == nums[i-1] {
				continue
			}

			comb = append(comb, nums[i])
			res = append(res, append([]int(nil), comb...))
			dfs(i + 1)
			comb = comb[:len(comb)-1]
		}
	}

	dfs(0)
	return res
}
